1. Technical Field of the Invention
The present invention generally relates to resilient packet rings (“RPRs”) and wavelength division multiplex RPRs (“WDMRPRs”). More particularly, and not by way of any limitation, the present invention is directed to a load balancing technique for use in RPRs and WDMRPRs.
2. Description of Related Art
Resilient Packet Ring (“RPR”) is a packet-based technology designed primarily for implementing metropolitan area networks (“MANs”). The basic topology of RPR is a dual counter-rotating ring in which both rings transport both data and control packets. WDMRPR is an RPR with more than one wavelength per ring. RPR technology includes a Medium Access Control (“MAC”) mechanism that controls access to the RPR.
FIG. 1 is an example RPR network 100 consisting of five nodes, respectively designated A–E, and two rings, illustrated in FIG. 1 as an outer ring X and an inner ring Y. Each node A–E is connected to its adjacent nodes via at least two links; one on the inner ring and one on the outer ring. Links on the inner ring are designated a–e, while links on the outer ring are designated α–ε. Accordingly, nodes A and B are connected by links α and e, nodes B and C are connected by links β and d, nodes C and D are connected by links γ and c, nodes D and E are connected by links δ and b, and nodes E and A are connected by links ε and a.
Information is carried in one and only one direction on a ring, either clockwise or counter-clockwise. As illustrated in FIG. 1, the outer ring X carries data and control packets in the clockwise direction and the inner ring Y carries data and control packets in the counter-clockwise direction. Features of RPR include spatial reuse and destination stripping, fast protection, media independent MAC, support for layer 2 devices (e.g., Ethernet switches) and layer 3 devices (e.g., routers). RPR operates as a distributed switch at layer 2. Alternatives to RPR include SONET/SDH rings and Ethernet switches. The former, implemented with routers, is expensive and inefficient for dynamic traffic patterns; however, it provides efficient protection. The latter offers no protection bandwidth or fairness, but does provide efficient bandwidth utilization. Moreover, in contrast to layer 3 devices, RPR has ring awareness. RPR, therefore, is intended to embody the best features of both SONET and Ethernet switches, that is, bandwidth efficiency, fairness, and fast protection. To realize these features, the RPR should provide a basic ring access mechanism, additional mechanisms to provide satisfactory performance for traffic transiting the ring, and appropriate protection features.
Several RPR terms and concepts will now be defined. Referring again to FIG. 1, assume that traffic destined for node D enters the ring at node A and passes through nodes B and C. Node A is referred to as the “ingress node”, node D is referred to as the “egress node”, and nodes B and C are referred to as “intermediate nodes.” As previously noted, the fiber connecting two nodes is referred to as a “link”. In WDMRPR, a wavelength between two nodes is referred to as a link. From the perspective of nodes B and C, traffic from node A is “ring traffic”. Traffic entering node B or C is referred to as “tributary traffic,” with respect to node A traffic.
At the ingress node, as soon as a flow is admitted to the RPR, an RPR header is created and attached to every packet within the flow. The RPR header contains a Class of Service (“CoS”) marking, a preemption bit, a ring identifier, and a destination MAC address. Each intermediate node will examine the incoming packet and perform an address lookup. If the packet is destined for the current node, it is taken off the ring at that node. If it is destined for some other node, it is placed back on to the ring.
One problem inherent in RPR architecture is the problem of load imbalance between two or more rings or wavelengths. Hereinafter, unless otherwise explicitly specified, the term “rings” will be deemed to encompass both rings and wavelengths. Load imbalance results from excessive traffic on one ring, as compared to little traffic on another ring. In an RPR with two rings, there are only two options for sending traffic from one node to another node, either on one ring or on the other. In such cases, traffic is typically sent on the ring with the fewest hops. This may result in a situation where a lot of traffic travels from one node to another on only one ring, because the ring has fewer hops as compared to the other ring.
Additionally, because RPR employs destination stripping, certain segments on one ring are typically more heavily loaded as compared to other segments on the same ring. Also, certain segments on one ring may be much more heavily loaded as compared to segments on the other ring.
As previously indicated, load imbalance may be defined as the concurrent overutilization of capacity on one or more links in the RPR and the underutilization of capacity of other links in the RPR. Load imbalance can be illustrated as follows. Referring again to FIG. 1, traffic going from node A to node B can travel either on the outer ring, via link α, or on the inner ring via links a, b, c, and d. For obvious reasons, traffic will tend to take the link α, since it is the more direct route. In the absence of any other traffic on the RPR, the link α will be overutilized, while the other links will be underutilized. The solution is to “load balance” the traffic between the links so that packets of a given class will experience approximately the same delay regardless of what the shortest path is.
Thus, traffic going from one node to another experiences varying amounts of delay depending on how many and which heavily loaded segments it traverses. Since traffic performance is judged by total end-to-end delay, the traffic performance (delay, dropped packets, etc.) on one ring may be significantly worse than the traffic performance on the other ring for a single class of service. This results in congestion on one ring versus unused capacity on the other ring and therefore requires load balancing.
Load balancing in RPR involves two functions: (a) diverting incoming flows from more heavily loaded rings to alternate paths on other rings, where they will likely experience more hops, but better performance, due to less traffic; and (b) improving the performance of existing traffic on the heavily loaded ring. Perfect load balancing in RPR, for all classes, between all pairs of nodes, is challenging due to the ring structure and destination stripping features of RPR. Load balancing performed for one pair of nodes for one class may result in traffic redistribution that might necessitate load balancing between another pair of nodes for the same or different traffic class. Dynamic traffic patterns and time-dependent flow arrivals and departures also complicate load balancing in RPR.
Prior art for load balancing traffic in multiple rings (or wavelengths) of RPR is currently not known to exist. Prior art for changing quality of service (“QoS”) parameters of various classes relative to one another is inadequate to help divert traffic to alternate paths on multiple rings. Prior art to change the token bucket (“TB”) parameters, including peak data rate and maximum burst size, for aggregate traffic flows does not allow the behavior of traffic classes to be changed relative to one another. While it may be adequate to reduce congestion in a network, it is inadequate to implement load balancing between rings in an RPR. Finally, all known prior art is restricted to only TB parameters and does not consider the interaction between the bandwidth broker (“BB”) parameters, which include allocated bandwidth, available bandwidth, and used bandwidth, and the QoS parameters, which include the TB parameters as well as the class based queuing (“CBQ”) parameters.